/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/expression-tree-build
   @Language: C++
   @Datetime: 19-04-10 10:58
   */

/**
 * Definition of ExpressionTreeNode:
 * class ExpressionTreeNode {
 * public:
 *     string symbol;
 *     ExpressionTreeNode *left, *right;
 *     ExpressionTreeNode(string symbol) {
 *         this->symbol = symbol;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
	typedef pair<ExpressionTreeNode*,int> ETNode;
	ExpressionTreeNode *add(stack<ETNode> &s, ETNode cur){
		ETNode prev(NULL,0);
		for(; s.size() && s.top().second>=cur.second; s.pop()){
			const auto &top=s.top();
			if(prev.first) top.first->right=prev.first;
			prev=top;
		}
		cur.first->left=prev.first;
		s.push(cur);
		return cur.first->left;
	}
public:
	/*
	 * @param expression: A string array
	 * @return: The root of expression tree
	 */
	ExpressionTreeNode * build(vector<string> &exps) {
		// write your code here
		stack<ETNode> s;
		for(int weight=0, i=0; i<exps.size(); ++i){
			if(isdigit(exps[i][0]) || exps[i].length()>1)
				add(s,{new ExpressionTreeNode(exps[i]),3+weight});
			else if(exps[i][0]=='+'||exps[i][0]=='-')
				add(s,{new ExpressionTreeNode(exps[i]),1+weight});
			else if(exps[i][0]=='*'||exps[i][0]=='/')
				add(s,{new ExpressionTreeNode(exps[i]),2+weight});
			else if(exps[i][0]=='(') weight+=2;
			else if(exps[i][0]==')') weight-=2;
		}
		ExpressionTreeNode etn("");
		return add(s,{&etn,0});
	}
};
